class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 1)
            return 1;
        vector<int>dp(n + 1, 0);
        dp[1] = 1;
        int p = 1;
        int q = 1;
        int m = 1;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = min(min(dp[p] * 2, dp[q] * 3), dp[m] * 5);
            if (dp[i] == dp[p] * 2)p++;
            if (dp[i] == dp[q] * 3)q++;
            if (dp[i] == dp[m] * 5)m++;
        }
        return dp[n];

    }
}; class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0)return  false;
        while (n % 2 == 0)n /= 2;
        while (n % 3 == 0)n /= 3;
        while (n % 5 == 0)n /= 5;
        return n == 1;

    }
}; class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int m = arr.size();
        vector<int>g(m, 1), f(m, 1);
        int res = 1;
        for (int i = 1; i < m; i++)
        {
            if (arr[i] > arr[i - 1])
                f[i] = g[i - 1] + 1;
            if (arr[i] < arr[i - 1])
                g[i] = f[i - 1] + 1;
            res = max(max(res, g[i]), f[i]);

        }
        return res;








    }
}; class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int m = nums.size();
        vector<int>dp(m);
        int sum = 0;
        for (int i = 2; i < m; i++)
        {
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            sum += dp[i];






        }
        return sum;







    }
}; class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>>dp(m + 1, vector<int>(n + 2, INT_MAX));
        for (int i = 0; i < n + 2; i++)
        {
            dp[0][i] = 0;
        }
        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                int x = dp[i - 1][j - 1];
                int y = dp[i - 1][j];
                int z = dp[i - 1][j + 1];
                dp[i][j] = min(min(x, y), z) + matrix[i - 1][j - 1];
            }
        }

        int ret = INT_MAX;
        for (int i = 0; i < n + 2; i++)
        {
            if (dp[m][i] < ret)
                ret = dp[m][i];




        }
        return ret;
















    }
}; class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int m = nums.size();
        vector<int>dp(m, 1);
        for (int i = 1; i < m; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }





            }




        }
        int ret = 1;
        for (int i = 0; i < m; i++)
        {
            if (dp[i] > ret)
                ret = dp[i];


        }
        return ret;


    }
}; class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int m = nums.size();
        int ret = 1;
        vector<int>f(m, 1), g(m, 1);
        for (int i = 1; i < m; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j]) f[i] = max(f[i], g[j] + 1);
                if (nums[i] < nums[j]) g[i] = max(g[i], f[j] + 1);
            }
            ret = max(max(ret, f[i]), g[i]);
        }

        return ret;
    }
};